Superliczby w permutacji
Limit pamięci: 32 MB
Permutacja
-elementowa jest ciągiem
-elementowym
składającym
się z różnych liczb ze zbioru
. Przykładowo,
ciąg
jest permutacją
-elementową.
W permutacjach liczb będą interesować nas najdłuższe rosnące podciągi.
W przykładowej permutacji mają one długość
i istnieją dokładnie dwa takie podciągi, a mianowicie
oraz
.
Superliczbą nazwiemy każdą liczbę, która należy do dowolnego
z najdłuższych rosnących podciągów. W permutacji
superliczbami są
, zaś liczba
superliczbą nie jest.
Twoim zadaniem jest dla zadanej permutacji znaleźć wszystkie
superliczby.
Zadanie
Napisz program, który:
- wczyta permutację ze standardowego wejścia,
- znajdzie wszystkie superliczby,
- wypisze znalezione superliczby na standardowe wyjście.
Wejście
Wejście składa się z dwóch wierszy. W pierwszym wierszu znajduję
się jedna liczba
,
.
W drugim wierszu znajduję się
liczb
tworzących permutację
-elementową, pooddzielanych pojedynczymi
odstępami.
Wyjście
Wyjście powinno się składać z dwóch wierszy. W pierwszym wierszu
powinna znaleźć się jedna liczba
- liczba superliczb
w wejściowej permutacji. W drugim
powinny znaleźć się superliczby pooddzielane pojedynczymi
odstępami, wymienione w kolejności rosnącej.
Przykład
Dla danych wejściowych:
5
2 1 4 5 3
poprawną odpowiedzią jest:
4
1 2 4 5
Autor zadania: Jakub Pawlewicz.